package xj.graph2d.graph;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.StringReader;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Set;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.parsers.ParserConfigurationException;

import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.Node;
import org.w3c.dom.NodeList;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;

public class AbstractGraph <NodeType extends GraphNode<EdgeType>, 
  			    EdgeType extends GraphEdge<NodeType>>
  extends AbstractSubgraph<NodeType, EdgeType> 
  implements Graph<NodeType, EdgeType> {

  public AbstractGraph() {
    this(null);
  }

  public AbstractGraph(String name) {
    super(name);
    setGraph(this);
  }

  public boolean isDirected() {
    return directed;
  }

  public void setDirected(boolean directed) {
    this.directed = directed;
  }

  public boolean isStrict() {
    return strict;
  }

  public void setStrict(boolean strict) {
    this.strict = strict;
  }

  /*
   * return true if there is a path from src to des
   */
  public boolean isReachable(NodeType src, NodeType des) {
    if (src != null && des != null) {
      if (src == des) {
	return true;
      }
      Set<NodeType> reachable = new HashSet<NodeType>();
      Set<NodeType> front = new HashSet<NodeType>();
      Set<NodeType> newset = new HashSet<NodeType>();
      newset.add(src);
      while (newset.size() > 0) {
	front.addAll(newset);
	newset.clear();
	Iterator<NodeType> iter = front.iterator();
	while (iter.hasNext()) {
	  NodeType node = iter.next();
	  if (node == des) {
	    return true;
	  }
	  Set<?> edges = leavingEdges(node);
	  if (edges != null) {
	    Iterator<?> eiter = edges.iterator();
	    while (eiter.hasNext()) {
	      EdgeType e = (EdgeType) eiter.next();
	      NodeType n = e.getDestination();
	      if (!reachable.contains(n) && !front.contains(n)) {
		newset.add(n);
	      }
	    }
	  }
	}
	reachable.addAll(front);
	front.clear();
      }
    }
    return false;
  }

  public void setGraphLayoutManager(GraphLayoutManager g) {
    graphLayoutManager = g;
  }

  public GraphLayoutManager getGraphLayoutManager() {
    return graphLayoutManager;
  }

  public void doLayout() {
    if (graphLayoutManager != null) {
      graphLayoutManager.doLayout();
    }
  }

  public void layoutEdges() {
    if (graphLayoutManager != null) {
      graphLayoutManager.layoutEdges();
    }
  }

  private static int pcount = 1;

  public void print() {
    System.out.println("AbstractGraph.print(): [" + pcount++ + "] ==== begin graph ====");
    printSubgraph(0);
    System.out.println("AbstractGraph.print(): ==== end graph ====");
  }

  @Override
  public String toString() {
    String nstr = "V = {";
    String estr = "E = {";
    boolean first = true;
    Iterator<?> niter = nodes();
    while (niter.hasNext()) {
      if (first) {
	first = false;
      } else {
	nstr += ", ";
      }
      nstr += (NodeType) niter.next();
    }

    first = true;
    Iterator<?> eiter = edges();
    while (eiter.hasNext()) {
      if (first) {
	first = false;
      } else {
	estr += ", ";
      }
      estr += (EdgeType) eiter.next();
    }
    return nstr + "}\n" + estr + "}";
  }

  /**
   * Output graph to specified Writer.
   * 
   * @param output
   *                the Writer for writing
   */
  public void printGraph(PrintWriter output) {
    PrintWriter out = null;

    if (output instanceof PrintWriter) {
      out = output;
    } else {
      out = new PrintWriter(output);
    }
    getGraph().printSubgraph(out);
    out.flush();
  }

  /**
   * Output graph to specified OutputStream. A convenience method to
   * accomodate the OuputStreams easily.
   * 
   * @param output
   *                the OutputStream for writing
   */
  public void printGraph(OutputStream output) {
    printGraph(new PrintWriter(output));
  }

  /**
   * The string used for indentation when printing out the graph.
   */
  public final static String INDENT_STRING = "  ";

  // used with getIndent, incrementIndent and decrementIndent
  private StringBuilder indent = null;

  /**
   * Get the current indent string.
   * 
   * @return the current indent string.
   */
  public String getIndent() {
    if (indent == null) {
      indent = new StringBuilder(5 * INDENT_STRING.length());
    }
    return (indent.toString());
  }

  /**
   * Increase the indent string by appending INDENT_STRING.
   * 
   * @see Graph#INDENT_STRING
   */
  public void incrementIndent() {
    if (indent == null) {
      indent = new StringBuilder(5 * INDENT_STRING.length());
    }
    indent.append(INDENT_STRING);
  }

  /**
   * Decrease the indent string by removing one INDENT_STRING.
   * 
   * @see Graph#INDENT_STRING
   */
  public void decrementIndent() {
    int len = indent.length();

    if (len == 0) {
      return;
    }

    if (len < INDENT_STRING.length()) {
      indent.setLength(0);
    } else {
      indent.setLength(len - INDENT_STRING.length());
    }
  }

  public void printGraph() {

  }

  /**
   * Set the PrintWriter for error messages.
   * 
   * @param errWriter
   *                the PrintWriter to use for error messages.
   * @return the previous PrintWriter used for error messages.
   * @see java.io.PrintWriter
   */
  public PrintWriter setErrorWriter(PrintWriter errWriter) {
    PrintWriter oldWriter = this.errWriter;
    this.errWriter = errWriter;
    return oldWriter;
  }

  /**
   * Get the current PrintWriter used for error messages.
   * 
   * @return the current PrintWriter used for error messages.
   * @see java.io.PrintWriter
   */
  public PrintWriter getErrorWriter() {
    return errWriter;
  }

  /**
   * Print the supplied message to the error output. Nothing happens if
   * the error output is set to null.
   * 
   * @param msg
   *                the message to print on the error output.
   * @see Graph#setErrorWriter(java.io.PrintWriter)
   */
  public void printError(String msg) {
    printError(msg, null);
  }

  /**
   * Print the supplied message and exception information to the error
   * output. Nothing happens if the error output is set to null.
   * 
   * @param msg
   *                the message to print on the error output.
   * @param ex
   *                if supplied, the stack trace associated with this
   *                exception is also printed.
   * @see Graph#setErrorWriter(java.io.PrintWriter)
   */
  public void printError(String msg, Exception ex) {
    if (getErrorWriter() == null) {
      return;
    }
    getErrorWriter().println("ERROR: " + msg);
    if (ex != null) {
      ex.printStackTrace(getErrorWriter());
    }
    getErrorWriter().flush();
  }

  protected boolean directed;

  protected boolean strict;

  protected GraphLayoutManager graphLayoutManager;

  // used for error message (when set by setErrorWriter)
  private PrintWriter errWriter = null;

  /* Added by Naveen Vemuri. May 3, 2003. */
  public String xgmmlLabel = "graph";

  public String getXGMMLLabel() {
    return this.xgmmlLabel;
  }

  public void writeXGMML(PrintWriter out) {
    try {
      DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
      DocumentBuilder parser = factory.newDocumentBuilder();
      Document doc = parser.newDocument();
      Element root = this.createXGMMLElement(doc);

      /* now write the xgmml. */
      out.println(root.toString());
      out.flush();
    } catch (ParserConfigurationException ex) {
      System.out.println("Caught a ParserConfigurationException in writeXGMML");
    }
  }

  public Element createXGMMLElement(Document doc) {
    Element graphElement = doc.createElement(XGMML_GRAPH_TAG);
    graphElement.setAttribute("directed", "1");
    graphElement.setAttribute("id", "1");
    graphElement.setAttribute("label", this.getXGMMLLabel());

    Hashtable<AbstractGraphNode<EdgeType>, String> nodeHash = 
      new Hashtable<AbstractGraphNode<EdgeType>, String>(); 
    /* a hashtable to keep track of the nodes.   */

    /* cycle through the nodes. */
    int count = 1;
    for (Iterator<?> i = this.nodes(); i.hasNext(); count++) {
      /* add the node to the xgmml. */
      AbstractGraphNode node = (AbstractGraphNode) i.next();
      graphElement = node.createXGMMLElement(graphElement, doc, count);

      /* add the node to the node hash. */
      nodeHash.put(node, new Integer(count).toString());
    }

    count = 1;
    for (Iterator<?> i = this.edges(); i.hasNext(); count++) {
      AbstractGraphEdge edge = (AbstractGraphEdge) i.next();
      graphElement = edge
	  .createXGMMLElement(graphElement, doc, nodeHash, count);
    }

    return graphElement;
  }

  public void readXGMML(FileReader fr) {
    BufferedReader in = new BufferedReader(fr);

    String xgmml = "";
    String input;
    try {
      do {
	input = in.readLine();
	if (input != null) {
	  xgmml += input;
	}
      } while (input != null);

      DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
      DocumentBuilder parser = factory.newDocumentBuilder();
      StringReader stringReader = new StringReader(xgmml);

      Document doc = parser.parse(new InputSource(stringReader));

      Element rootElement = doc.getDocumentElement();

      this.createGraph(rootElement, doc);
    } catch (IOException ex) {
      System.out.println("Caught an IOException in readXGMML.");
    } catch (ParserConfigurationException ex) {
      System.out.println("Caught a ParserConfigurationException in readXGMML.");
    } catch (SAXException ex) {
      System.out.println("Caught a SAXException in readXGMML.");
    }
  }

  public void createGraph(Element rootElement, Document doc) {
    /* now parse through the xgmml. */
    Hashtable<String, NodeType> nodeHash = 
      new Hashtable<String, NodeType>();

    NodeList nodeChildren = this.getChildren(rootElement, doc, XGMML_NODE_TAG);
    for (int i = 0; i < nodeChildren.getLength(); i++) {
      Element e = (Element) nodeChildren.item(i);
      String name = e.getAttribute("name");
      String label = e.getAttribute("label");
      String id = e.getAttribute("id");

      NodeType node = (NodeType) new AbstractGraphNode<EdgeType>(name);
      this.addNode(node);

      nodeHash.put(id, node);
    }

    NodeList edgeChildren = this.getChildren(rootElement, doc, XGMML_EDGE_TAG);
    for (int i = 0; i < edgeChildren.getLength(); i++) {
      Element e = (Element) edgeChildren.item(i);
      String name = e.getAttribute("weight");
      String label = e.getAttribute("label");
      String source = e.getAttribute("source");
      String target = e.getAttribute("target");

      NodeType src = nodeHash.get(source);
      NodeType tar = nodeHash.get(target);

      EdgeType edge = (EdgeType) new AbstractGraphEdge<NodeType>(src, tar);
      this.addEdge(edge);
    }
  }

  public NodeList getChildren(Element parentElement, Document doc,
			      String tagName) {
    NodeList children = parentElement.getChildNodes();
    Element el = doc.createElement(parentElement.getNodeName());
    for (int i = 0; i < children.getLength(); i++) {
      Node n = children.item(i);
      if (n.getNodeName().equals(tagName)) {
	el.appendChild(n.cloneNode(true));
      }
    }

    return el.getChildNodes();
  }
  /* End of additions. */

}
